package MinLoad;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class MinMutation {
    char[] change = new char[]{'A', 'C', 'G', 'T'};

    public int code(String startGene, String endGene, String[] bank) {

        //预处理一下基因库
        Set<String> hashBank = new HashSet<>();
        Set<String> vis = new HashSet<>();  //已经搜索过的状态
        for (int i = 0; i < bank.length; i++){
            hashBank.add(bank[i]);
        }

        if (startGene.equals(endGene)){
            return 0;
        }

        if (!hashBank.contains(endGene)){
            return -1;
        }


        Queue<String> q = new LinkedList<>();
        q.add(startGene);
        vis.add(startGene);
        int step = 0;

        while (!q.isEmpty()){
            step++;
            int sz = q.size();

            for (int i = 0; i < sz; i++){
                String t = q.poll();

                for (int j = 0; j < 8; j++){
                    char[] tmp = t.toCharArray();

                    for (int k = 0; k < 4; k++){
                        tmp[j] = change[k];
                        String next = new String(tmp);

                        if (hashBank.contains(next) && !vis.contains(next)){
                            if (next.equals(endGene)){
                                return step;
                            }

                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }


        return -1;
    }
}
